import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 09
 * Time: 11:03
 */
//牛客 字符串的排列
public class Solution2 {
    //官方推荐方法
    static boolean[] check;
    static StringBuilder path;
    static ArrayList<String> ret;
    public static ArrayList<String> Permutation (String str) {
        ret = new ArrayList<>();
        check = new boolean[str.length()];
        path= new StringBuilder();
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        dfs(arr);
        return ret;
    }
    public static void dfs(char[] arr) {
        if(path.length() == arr.length) {
            ret.add(new String(path.toString()));
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if(!check[i] && (i == 0 || arr[i] != arr[i - 1] || check[i - 1] == true)) {//i==0||str.charAt(i)!=str.charAt(i-1)||check[i-1]==true要用()包起来，作为前面&&的第二个条件
                path.append(arr[i]);
                check[i] = true;
                dfs(arr);
                check[i] = false;
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}
